The present invention relates to the field of instruction controlled digital computers and specifically to methods and apparatus associated with storage units in data processing systems.
Recent data processing systems have been designed with virtual storage in which different user programs are operable in the system. The programs identify storage locations with logical addresses. The logical addresses are translated dynamically to real addresses during the processing of instructions. Dynamic address translation is particularly important in multi-programming environments since different programs are free to use the same logical addresses. To avoid interference, the system must translate logical addresses, which are not unique, to real addresses which are unique for each executing program.
In order to provide for the uniqueness of the real addresses when non-unique logical addresses are employed, translation tables which are unique for each program are provided. The translation tables are typically stored in main storage. The accessing of the translation tables in main storage, however, requires a significant amount of time which can degrade system performance. In order to enhance the performance when translations are made, it is desirable to store translated information in high-speed buffers in order to reduce the number of accesses to main storage.
It is common in data processing systems to have a memory hierarchy wherein buffer memories of relatively low capacity, but of relatively high speed, operate in cooperation with main memories of relatively high capacity but of relatively low speed. It is desired that the vast majority of accesses, either to fetch or store information, be from the buffer memory so that the overall access time of the system is enhanced. In order to have the vast majority of accesses come from the relatively fast buffer memory, information is exchanged between the main memory and the buffer memory in accordance with predetermined algorithms.
In virtual storage, multi-programming systems, it is also desirable to store information in the buffer memory to reduce accesses to main store. In addition to real addresses of data and the data itself, the buffer memory stores logical addresses and program identifiers. With this information in the buffer memory, relatively more time consuming accesses to main storage for the same information are avoided.
The efficiency with which a buffer memory works in decreasing the access time of the overall system is dependent on a number of variables. For example, the variables include the capacity of the buffer memory, the capacity of the main store, the data transfer rate between stores, the replacement algorithms which determine when transfers between the main store and buffer are made, and the virtual-to-real address translation methods and apparatus.
In prior art systems, the address space of the buffer memory and the main store has been the real address space. Therefore, each virtual address from a program required address translation in order to access either the buffer or main store.
There is a need for improved buffer memory systems which are particularly suitable for virtual storage and for multi-programming data processing systems. Specifically, there is a need in such systems for memory hierarchies which have improved methods and apparatus for managing data transfers and for increasing the efficiency of operation.
In one data processing system, a high-speed buffer is addressed using virtual addresses. In such virtual addressed systems, the excess time of the overall system is enhanced since there is no need for a virtual-to-real address translation whenever the virtually addressed location is resident in the high-speed buffer.
In such virtually addressed systems, however, there is a need for addressing mechanisms which are economical to build and operate efficiently so as not to degrade the performance of the system.
In view of the above background, there is a need for new and improved mechanisms which are particularly useful in systems using virtual addressing.